package cuiyt.leetcode.dichotomy.democ;


import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author cyt
 * @create 2020-09-24 18:13
 */
public class Tc3 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> collect = Arrays.stream(arr).boxed().collect(Collectors.toList());

        int len = collect.size();
        if (x <= collect.get(0)) {
            return collect.subList(0, k);
        } else if (collect.get(len - 1) <= x) {
            return collect.subList(len - k, len);
        } else {


            /**
             * 找到大一点点元素
             */
            int index = Collections.binarySearch(collect, x);
            int low = Math.max(0, index - k - 1), high = Math.min(collect.size() - 1, collect.size() + k - 1);

            while (high - low > k - 1) {
                int min = x - collect.get(low);
                int max = collect.get(high) - x;

                if (max >= min) {
                    high--;
                } else {
                    low++;
                }
            }
            return collect.subList(low, high + 1);
        }
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        new Tc3().findClosestElements(arr, 4, 3).forEach(System.out::println);
    }
}
